/**
 * @author LKQ
 * @date 2021/11/29 10:23
 * @description 利用递归，如果空链表，直接返回另一个链表；否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，
 * 然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
 */
public class FormalSolution {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        FormalSolution formalSolution = new FormalSolution();
        formalSolution.mergeTwoLists(l1, l2);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

